1. Field of the Invention
The present invention relates generally to the field of high speed data transfer, and more specifically to methods and apparatus for efficiently implementing VoQs for different classes of service in a high speed IP router environment.
2. Description of the Related Art
Data communication networks receive and transmit ever increasing amounts of data. Data is transmitted from an originator or requester through a network to a destination, such as a router, switching platform, other network, or application. Along this path may be multiple transfer points, such as hardware routers, that receive data typically in the form of packets or data frames. At each transfer point data must be routed to the next point in the network in a rapid and efficient manner. Certain protocols or standards may be employed in transferring data from one point to another, and such standards enable hardware and software using different configurations to effectively receive and transfer the data. Such standards include, but are not limited to, standards promulgated by the ITU (International Telecommunications Union) and ANSI (American National Standards Institute).
The points through the data network operate to receive data frames or packets from various requesters and provide results or satisfy requests in an orderly and efficient manner. Frames or packets including requests for access to resources may arrive synchronously or asynchronously. Requests may be for access to multiple resources or channels or to particular sets of resources or channels.
FIG. 1 illustrates one challenge inherent in such a system. One transfer point in the network, such as a router, may receive packets such as packet 101 from multiple queues, such as queue 102. Queues may receive packets over multiple channels, such as channel 103. All packets received from the queues over the various channels are provided from the router in an ordered manner, such as via an output list. The desired output list provided is a single common output list 105, such as a VoQ. VoQs collect the queue information for all channels and transmit the output list information across the common output port.
In different applications, different incoming requests may be accorded different classes of service, some classes having higher priority than others. The data received may take different forms, including different packet sizes and related parameters. Packets may arrive from multiple queues, each packet having a specific class of service.
The problem with such a multiple class of service VoQ arrangement is that simply queuing the incoming requests in a FIFO (first in, first out) manner can result in inefficiencies, the most notable inefficiency being timing required to assess the quality of the packet, assemble the queue, and prepare the data for transfer. Such a process can require multiple seeks to memory, as received packets may be stored in memory, or enqueued, read from memory, or dequeued, and then transmitted.
Previous systems have employed a FIFO design which queues the packet upon receipt of the first bytes of a packet. This type of system can encounter delays if the packet is incomplete or interrupted. Such an imperfect packet must either be repaired or discarded, and either action decreases throughput and system performance. Alternately, systems have employed FIFO logic based on the timing of the last bits of the packet received. In many circumstances, this too can result in inefficiencies; for example, in the case of a damaged packet, packet length and error information is not available until the end of the packet. These inefficiencies, among others, result in an excessive number of memory accesses to manage the different VoQs, which is undesirable.
With the current state of internet traffic, and in view of the significant latency associated with enqueueing, dequeueing, and transmitting output queues on currently available memory devices, it would be desirable to provide a system and method that would improve the maximum attainable transmission rate of network processors, traffic managers, or other devices employing VoQs or other queuing arrangements over those systems and methods previously offered.